home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / incl / LEDA / impl / bin_heap.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  2.2 KB  |  108 lines

  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  bin_heap.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. *******************************************************************************/
  13.  
  14.  
  15. #ifndef LEDA_BIN_HEAP_H
  16. #define LEDA_BIN_HEAP_H
  17.  
  18. //------------------------------------------------------------------------------
  19. // binary Heaps
  20. //
  21. // S. Naeher (1993)
  22. //
  23. //------------------------------------------------------------------------------
  24.  
  25.  
  26. #include <LEDA/basic.h>
  27.  
  28.  
  29. class bin_heap_elem
  30. {
  31.   friend class bin_heap;
  32.  
  33.   GenPtr key;
  34.   GenPtr inf;
  35.  
  36.   int index;
  37.  
  38.   bin_heap_elem(GenPtr k, GenPtr i, int pos) { key = k; inf = i; index = pos; }
  39.  
  40.   LEDA_MEMORY(bin_heap_elem)
  41.  
  42. };
  43.  
  44.  
  45. typedef bin_heap_elem* bin_heap_item;
  46.  
  47.  
  48. class bin_heap  {
  49.  
  50. virtual int  cmp(GenPtr x, GenPtr y) const { return compare(x,y); }
  51. virtual void copy_key(GenPtr&)   const {}
  52. virtual void copy_inf(GenPtr&)   const {}
  53. virtual void clear_key(GenPtr&)  const {}
  54. virtual void clear_inf(GenPtr&)  const {}
  55. virtual void print_key(GenPtr x) const { Print(x); }
  56. virtual void print_inf(GenPtr x) const { Print(x); }
  57.  
  58. virtual int  int_type() const { return 0; }
  59.  
  60.  
  61. int          count;
  62. int          max_size;
  63.  
  64. bin_heap_item* HEAP;
  65.  
  66.  
  67. void rise(int,bin_heap_item);
  68. void sink(int,bin_heap_item);
  69.  
  70. protected:
  71.  
  72. bin_heap_item item(GenPtr p) const { return bin_heap_item(p); }
  73.  
  74. public:
  75.  
  76. bin_heap_item insert(GenPtr, GenPtr);
  77. bin_heap_item find_min()  const      { return HEAP[1];  }
  78. bin_heap_item first_item() const     { return HEAP[1]; }
  79. bin_heap_item next_item(bin_heap_item it) const { return HEAP[it->index+1];}
  80.  
  81. void decrease_key(bin_heap_item, GenPtr);
  82. void change_inf(bin_heap_item, GenPtr);
  83. void del_item(bin_heap_item);
  84. void del_min() { del_item(find_min()); }
  85.  
  86. GenPtr key(bin_heap_item it) const { return it->key; }
  87. GenPtr inf(bin_heap_item it) const { return it->inf; }
  88.  
  89. int  size()    const  { return count;    }
  90. bool empty()   const  { return count==0; }
  91.  
  92. void clear();
  93. void print();
  94.  
  95. bin_heap& operator=(const bin_heap&);
  96.  
  97. bin_heap(int n = 1024);  // default start size 
  98. bin_heap(const bin_heap&);
  99.  
  100. bin_heap(int,int) {}
  101.  
  102. virtual ~bin_heap();
  103.  
  104. };
  105.  
  106. #endif
  107.